// list standard header -*-c++-*-
// Copyright 2003-2010 IAR Systems AB. 
#ifndef _LIST_
#define _LIST_

#ifndef _SYSTEM_BUILD
#pragma system_include
#endif

#include <functional>
#include <memory>
#include <stdexcept>
_STD_BEGIN

#pragma language = save
#pragma language = extended
// The generic part of list
template<typename _Alloc>
struct __memory_of(typename _Alloc::value_type) _List_value
  : _ClassUtil::_AllocHolder<_Alloc, !_ClassUtil::_IsZeroSize<_Alloc>::_Result>
{
  struct __memory_of(typename _Alloc::value_type) _GenNode;

  typedef _List_value<_Alloc> _Myt;
  typedef typename _Alloc::template rebind< _GenNode >::other _GnalTy;
//  typedef typename _GnalTy::pointer   _Genptr;
  typedef _GenNode * _Genptr;
  typedef typename _TypeUtil::_CopyMemory<typename _Alloc::value_type,
                                          _Genptr>::_Type &
          _Genpref;
  typedef typename _GnalTy::size_type size_type;

  struct __memory_of(typename _Alloc::value_type) _GenNode
  {       // list node
    _GenNode(_Genptr _Nextarg, _Genptr _Prevarg) 
      : _Next(_Nextarg), _Prev(_Prevarg)
    {}      // construct a node, no value

    _Genptr _Next;  // successor node, or first element if head
    _Genptr _Prev;  // predecessor node, or last element if head

  protected:
    ~_GenNode()       // To protect against dangerous deletion
    {}

    friend struct _List_value;
  };

  _List_value()
    : _Myhead(&_Myhead, &_Myhead), _Mysize(0)
  {}
  _List_value(_Alloc _Al)
    : _ClassUtil::_AllocHolder<_Alloc,
                               !_ClassUtil::_IsZeroSize<_Alloc>::_Result>(_Al),
      _Myhead(&_Myhead, &_Myhead),
      _Mysize(0)
  {}

//  _Alloc       & _Alval()       { return *this; }
//  _Alloc const & _Alval() const { return *this; }
  _GnalTy        _Alty ()       { return _GnalTy(this->_Alval()); }

  void _Disconnect(_Genptr _Pnode)
  {
    _Pnode->_Prev->_Next = _Pnode->_Next;
    _Pnode->_Next->_Prev = _Pnode->_Prev;
    --this->_Mysize; 
  }

  _Genptr _Begin() { return _Myhead._Next; }
  _Genptr _End() { return &_Myhead; }

  static _Genpref _Next(_Genptr _Ptr) { return _Ptr->_Next; }
  static _Genpref _Prev(_Genptr _Ptr) { return _Ptr->_Prev; }

  void _Reverse()
  {       // reverse sequence
    if (2 <= _Mysize)
    {       // worth doing
      _Genptr _Last = _End();
      for (_Genptr _Next = _Begin()->_Next; _Next != _Last; )
      {       // move next element to beginning
        _Genptr _Before = _Next;
        _Next = _Next->_Next;
        _Splice(_Begin(), *this, _Before, _Next, 1); 
      }
    }
  }

  void _Splice(_Genptr _Where, _Myt& _Right,
               _Genptr _First, _Genptr _Last, size_type _Count)
  {       // splice _Right [_First, _Last) before _Where
    if (this != &_Right)
    {       // splicing from another list, adjust counts
      _Incsize(_Count);
      _Right._Mysize -= _Count; 
    }
    _Next(_Prev(_First)) = _Last;
    _Next(_Prev(_Last)) = _Where;
    _Next(_Prev(_Where)) = _First;
    _Genptr _Pnode = _Prev(_Where);
    _Prev(_Where) = _Prev(_Last);
    _Prev(_Last) = _Prev(_First);
    _Prev(_First) = _Pnode; 
  }

  void _Incsize(size_type _Count)
  {       // alter element count, with checking
    if (_Alty().max_size() - _Mysize < _Count)
      _THROW(length_error, "list<T> too long");
    this->_Mysize += _Count; 
  }

  void swap(_Myt & _Right)
  {
    using _STD swap;
    _Genptr _P1 = _Myhead._Prev;
    _Myhead._Next->_Prev = &_Right._Myhead;
              _P1->_Next = &_Right._Myhead;
    _Genptr _P2 = _Right._Myhead._Prev;
    _Right._Myhead._Next->_Prev = &_Myhead;
                     _P2->_Next = &_Myhead;
    /*_STD*/ swap(_Myhead._Next, _Right._Myhead._Next);
    /*_STD*/ swap(_Myhead._Prev, _Right._Myhead._Prev);
    /*_STD*/ swap(_Mysize,       _Right._Mysize);
  }

  _GenNode _Myhead;
  size_type _Mysize;      // number of elements
};

// TEMPLATE CLASS list
template<class _Ty,
         class _Ax = allocator<_Ty> >
class list
  : private _List_value<typename _Ax::template rebind<
                 typename _TypeUtil::_CopyMemory<_Ty, void>::_Type
                                                     >::other>
{       // bidirectional linked list
  typedef typename _TypeUtil::_ParameterType<_Ty>::_Type _ParamTy;
public:
  typedef list<_Ty, _Ax> _Myt;
  typedef _List_value<typename _Ax::template rebind<
               typename _TypeUtil::_CopyMemory<_Ty, void>::_Type
                                                   >::other> _Mybase;
  typedef typename _Ax::template rebind<_Ty>::other _Alloc;
  typedef typename _TypeUtil::_StripMemory<_Ty>::_Type _BaseTy;

protected:
  typedef typename _Mybase::_Genptr _Genptr;

  struct __memory_of(_Ty) _Node;
  friend struct __memory_of(_Ty)  _Node;

  struct __memory_of(_Ty) _Node : _Mybase::_GenNode
  {
    _Node(_Genptr _Nextarg, _Genptr _Prevarg, _ParamTy _Val)
      : _Mybase::_GenNode(_Nextarg, _Prevarg),
        _Myval(_Val)
    {}
    _BaseTy _Myval;
  };

//  typedef _POINTER_X(_Node, _Alloc) _Nodeptr;
#pragma important_typedef
  typedef _Node * _Nodeptr;
//  typedef _CPOINTER_X(_Node, _Alloc) _CNodeptr;
  typedef _Node const * _CNodeptr;
//  typedef _REFERENCE_X(_Nodeptr, _Alloc) _Nodepref;
  typedef typename _TypeUtil::_CopyMemory<_Ty, _Nodeptr>::_Type _Nodepmem;
  typedef _Nodepmem & _Nodepref;
  typedef typename _Alloc::reference _Vref;

  _Nodeptr _Head()
  {
    return static_cast<_Nodeptr>(&this->_Myhead);
  }

  _CNodeptr _Head() const
  {
    return static_cast<_CNodeptr>(&this->_Myhead);
  }

  // Use when constructing a const_iterator.
  _Nodeptr _XHead() const
  {
    return const_cast<_Nodeptr>(_Head());
  }

  static _Nodepref _Next(_Genptr _Pnode)
  {       // return reference to successor pointer in node
    (void)static_cast<_Nodeptr>(_Pnode->_Next);  // Error trap
    (void)static_cast<_Genptr &>(_Pnode->_Next); // Error trap
    return reinterpret_cast<_Nodepref>(_Pnode->_Next);
  }

  static _Nodepref _Prev(_Genptr _Pnode)
  {       // return reference to predecessor pointer in node
    (void)static_cast<_Nodeptr>(_Pnode->_Prev);  // Error trap
    (void)static_cast<_Genptr &>(_Pnode->_Prev); // Error trap
    return reinterpret_cast<_Nodepref>(_Pnode->_Prev);
  }

  static _Vref _Myval(_Genptr _Pnode)
  {       // return reference to value in node
    return static_cast<_Vref>(static_cast<_Nodeptr>(_Pnode)->_Myval);
  }

  typedef typename _Alloc::template rebind<_Node>::other _AlNodTy;
  _AlNodTy _Alnod() const { return _AlNodTy(this->_Alval()); }

public:
  typedef _Alloc allocator_type;
  typedef typename _Alloc::size_type size_type;
  typedef typename _Alloc::difference_type _Dift;
  typedef _Dift difference_type;
  typedef typename _Alloc::pointer _Tptr;
  typedef typename _Alloc::const_pointer _Ctptr;
  typedef _Tptr pointer;
  typedef _Ctptr const_pointer;
  typedef typename _Alloc::reference _Reft;
  typedef _Reft reference;
  typedef typename _Alloc::const_reference const_reference;
#pragma important_typedef
  typedef typename _Alloc::value_type value_type;

  // CLASS const_iterator
  class const_iterator;
  friend class const_iterator;

  class const_iterator
    : public _Bidit<_Ty, _Dift, _Ctptr, const_reference>
  {       // iterator for nonmutable list
  public:
    typedef bidirectional_iterator_tag iterator_category;
#pragma important_typedef
    typedef _Ty value_type;
    typedef _Dift difference_type;
    typedef _Ctptr pointer;
    typedef const_reference reference;

    const_iterator()
      : _Ptr(0)
    {}      // construct with null node pointer

    const_iterator(_Nodeptr _Pnode)
      : _Ptr(_Pnode)
    {}      // construct with node pointer _Pnode

    const_reference operator*() const
    {       // return designated value
      return (_Myval(_Ptr)); 
    }

    _Ctptr operator->() const
    {       // return pointer to class object
      return (&**this); 
    }

    const_iterator& operator++()
    {       // preincrement
      _Ptr = _Next(_Ptr);
      return (*this); 
    }

    const_iterator operator++(int)
    {       // postincrement
      const_iterator _Tmp = *this;
      ++*this;
      return (_Tmp); 
    }

    const_iterator& operator--()
    {       // predecrement
      _Ptr = _Prev(_Ptr);
      return (*this); 
    }

    const_iterator operator--(int)
    {       // postdecrement
      const_iterator _Tmp = *this;
      --*this;
      return (_Tmp); 
    }

    bool operator==(const const_iterator& _Right) const
    {       // test for iterator equality
      return (_Ptr == _Right._Ptr); 
    }

    bool operator!=(const const_iterator& _Right) const
    {       // test for iterator inequality
      return (!(*this == _Right)); 
    }

    _Nodeptr _Mynode() const
    {       // return node pointer
      return (_Ptr); 
    }

  protected:
    _Nodeptr _Ptr;  // pointer to node
  };

  // CLASS iterator
  class iterator;
  friend class iterator;

  class iterator
    : public const_iterator
  {       // iterator for mutable list
  public:
    typedef bidirectional_iterator_tag iterator_category;
#pragma important_typedef
    typedef _Ty value_type;
    typedef _Dift difference_type;
    typedef _Tptr pointer;
    typedef _Reft reference;

    iterator()
      : const_iterator(0)
    {}      // construct with null node

    iterator(_Nodeptr _Pnode)
      : const_iterator(_Pnode)
    {}      // construct with node pointer _Pnode

    reference operator*() const
    {       // return designated value
      return (_Myval(this->_Ptr)); 
    }

    _Tptr operator->() const
    {       // return pointer to class object
      return (&**this); 
    }

    iterator& operator++()
    {       // preincrement
      this->_Ptr = _Next(this->_Ptr);
      return (*this); 
    }

    iterator operator++(int)
    {       // postincrement
      iterator _Tmp = *this;
      ++*this;
      return (_Tmp); 
    }

    iterator& operator--()
    {       // predecrement
      this->_Ptr = _Prev(this->_Ptr);
      return (*this); 
    }

    iterator operator--(int)
    {       // postdecrement
      iterator _Tmp = *this;
      --*this;
      return (_Tmp); 
    }
  };

  typedef _STD reverse_iterator<iterator> reverse_iterator;
  typedef _STD reverse_iterator<const_iterator> const_reverse_iterator;

  list()
    : _Mybase()
  {}      // construct empty list

  explicit list(const _Alloc& _Al)
    : _Mybase(_Al)
  {}      // construct empty list, allocator

  explicit list(size_type _Count)
    : _Mybase()
  {       // construct list from _Count * _Ty()
    _Construct_n(_Count, typename _ClassUtil::_TmpHolder<_Ty>::_Type()); 
  }

  list(size_type _Count, _ParamTy _Val)
    : _Mybase()
  {       // construct list from _Count * _Val
    _Construct_n(_Count, _Val); 
  }

  list(size_type _Count, _ParamTy _Val, const _Alloc& _Al)
    : _Mybase(_Al)
  {       // construct list, allocator from _Count * _Val
    _Construct_n(_Count, _Val); 
  }

  list(const _Myt& _Right)
    : _Mybase(_Right._Alval())
  {       // construct list by copying _Right
    _TRY_BEGIN
    insert(begin(), _Right.begin(), _Right.end());
    _CATCH_ALL
    _Tidy();
    _RERAISE;
    _CATCH_END 
  }

  template<class _Iter>
  list(_Iter _First,
       _ALLOW_ONLY_ITERATORS(_Iter, _Iter) _Last)
    : _Mybase()
  {       // construct list from [_First, _Last)
    _Construct(_First, _Last);
  }

  template<class _Iter>
  list(_Iter _First,
       _ALLOW_ONLY_ITERATORS(_Iter, _Iter) _Last,
       const _Alloc& _Al)
    : _Mybase(_Al)
  {       // construct list, allocator from [_First, _Last)
    _Construct(_First, _Last);
  }

  template<class _Iter>
  void _Construct(_Iter _First, _Iter _Last)
  {       // construct list from [_First, _Last), input iterators
    _TRY_BEGIN
    insert(begin(), _First, _Last);
    _CATCH_ALL
    _Tidy();
    _RERAISE;
    _CATCH_END 
  }

  void _Construct_n(size_type _Count, _ParamTy _Val)
  {       // construct from _Count * _Val
    _TRY_BEGIN
    _Insert_n(begin(), _Count, _Val);
    _CATCH_ALL
    _Tidy();
    _RERAISE;
    _CATCH_END 
  }

  ~list()
  {       // destroy the object
    _Tidy(); 
  }

  _Myt& operator=(const _Myt& _Right)
  {       // assign _Right
    if (this != &_Right)
      assign(_Right.begin(), _Right.end());
    return (*this); 
  }

  iterator begin()
  {       // return iterator for beginning of mutable sequence
    return (iterator(_Next(_Head())));
  }

  const_iterator begin() const
  {       // return iterator for beginning of nonmutable sequence
    return (const_iterator(_Next(_XHead())));
  }

  iterator end()
  {       // return iterator for end of mutable sequence
    return (iterator(_Head()));
  }

  const_iterator end() const
  {       // return iterator for end of nonmutable sequence
    return (const_iterator(_XHead()));
  }

  reverse_iterator rbegin()
  {       // return iterator for beginning of reversed mutable sequence
    return (reverse_iterator(end())); 
  }

  const_reverse_iterator rbegin() const
  {       // return iterator for beginning of reversed nonmutable sequence
    return (const_reverse_iterator(end())); 
  }

  reverse_iterator rend()
  {       // return iterator for end of reversed mutable sequence
    return (reverse_iterator(begin())); 
  }

  const_reverse_iterator rend() const
  {       // return iterator for end of reversed nonmutable sequence
    return (const_reverse_iterator(begin())); 
  }

  void resize(size_type _Newsize)
  {       // determine new length, padding with _Ty() elements as needed
    resize(_Newsize, typename _ClassUtil::_TmpHolder<_Ty>::_Type());
  }

  void resize(size_type _Newsize, _ParamTy _Val)
  {       // determine new length, padding with _Val elements as needed
    if (size() < _Newsize)
      _Insert_n(end(), _Newsize - size(), _Val);
    else
      while (_Newsize < size())
        pop_back(); 
  }

  size_type size() const
  {       // return length of sequence
    return (this->_Mysize); 
  }

  size_type max_size() const
  {       // return maximum possible length of sequence
    return (this->_Alnod().max_size()); 
  }

  bool empty() const
  {       // test if sequence is empty
    return (this->_Mysize == 0); 
  }

  allocator_type get_allocator() const
  {       // return allocator object for values
    return (this->_Alval());
  }

  reference front()
  {       // return first element of mutable sequence
    return (*begin()); 
  }

  const_reference front() const
  {       // return first element of nonmutable sequence
    return (*begin()); 
  }

  reference back()
  {       // return last element of mutable sequence
    return (*(--end())); 
  }

  const_reference back() const
  {       // return last element of nonmutable sequence
    return (*(--end())); 
  }

  void push_front(_ParamTy _Val)
  {       // insert element at beginning
    _Insert(begin(), _Val); 
  }

  void pop_front()
  {       // erase element at beginning
    erase(begin()); 
  }

  void push_back(_ParamTy _Val)
  {       // insert element at end
    _Insert(end(), _Val); 
  }

  void pop_back()
  {       // erase element at end
    erase(--end()); 
  }

  template<class _Iter>
  _ALLOW_ONLY_ITERATORS(_Iter, void)
  assign(_Iter _First, _Iter _Last)
  {       // assign [_First, _Last)
    erase(begin(), end());
    insert(begin(), _First, _Last); 
  }

  void assign(size_type _Count, _ParamTy _Val)
  {       // assign _Count * _Val
    _Assign_n(_Count, _Val); 
  }

  iterator insert(iterator _Where, _ParamTy _Val)
  {       // insert _Val at _Where
    _Insert(_Where, _Val);
    return (--_Where); 
  }

  void _Insert0(iterator _Where, _ParamTy _Val)
  {       // insert _Val at _Where
    _Nodeptr _Pnode = _Where._Mynode();
    _Nodeptr _Newnode = _Buynode(_Pnode, _Prev(_Pnode), _Val);
    _Incsize(1);
    _Prev(_Pnode) = _Newnode;
    _Next(_Prev(_Newnode)) = _Newnode; 
  }
  void _Insert(iterator _Where, _ParamTy _Val)
  {       // insert _Val at _Where
    _Insert0(_Where, _Val);
  }
#pragma basic_template_matching
  template<typename _Ty1>
  void _Insert(iterator _Where, _Ty1 const & _Val)
  {       // insert _Val at _Where. _Ty1 is not the correct type.
    typename _ClassUtil::_TmpHolder<_Ty>::_Type _Tmp(_Val);
    _Insert0(_Where, _Tmp);
  }

  void insert(iterator _Where, size_type _Count, _ParamTy _Val)
  {       // insert _Count * _Val at _Where
    _Insert_n(_Where, _Count, _Val); 
  }

#pragma basic_template_matching
  template<class _Iter>
  _ALLOW_ONLY_ITERATORS(_Iter, void)
  insert(iterator _Where, _Iter _First, _Iter _Last)
  {       // insert [_First, _Last) at _Where
    size_type _Num = 0;

    _TRY_BEGIN
    for (; _First != _Last; ++_First, ++_Num)
      _Insert(_Where, *_First);
    _CATCH_ALL
    for (; 0 < _Num; --_Num)
    {       // undo inserts
      iterator _Before = _Where;
      erase(--_Before); 
    }
    _RERAISE;
    _CATCH_END 
  }

  iterator erase(iterator _Where)
  {       // erase element at _Where
    _Nodeptr _Pnode = _Where._Mynode();
    ++_Where;
    if (_Pnode != &this->_Myhead)
    {       // not list head, safe to erase
      // We cannot do the deallocate in _List_value, since it needs the
      // correct type.
      _Mybase::_Disconnect(_Pnode);
      this->_Alnod().destroy(_Pnode);
      this->_Alnod().deallocate(_Pnode, 1);
    }
    return (_Where);
  }

  iterator erase(iterator _First, iterator _Last)
  {       // erase [_First, _Last)
    while (_First != _Last)
      erase(_First++);
    return (_First); 
  }

  void clear()
  {       // erase all
    erase(begin(), end()); 
  }

  void swap(_Myt& _Right)
  {       // exchange contents with _Right
    if (this->_Alval() == _Right._Alval())
    {       // same allocator, swap control information
      _Mybase::swap(_Right);
    }
    else
    {       // different allocator, do multiple assigns
      iterator _Where = begin();
      splice(_Where, _Right);
      _Right.splice(_Right.begin(), *this, _Where, end()); 
    }
  }

  void splice(iterator _Where, _Myt& _Right)
  {       // splice all of _Right at _Where
    if (this != &_Right && !_Right.empty())
    {       // worth splicing, do it
      _Splice(_Where, _Right, _Right.begin(), _Right.end(),
              _Right._Mysize);
    }
  }

  void splice(iterator _Where, _Myt& _Right, iterator _First)
  {       // splice _Right [_First, _First + 1) at _Where
    iterator _Last = _First;
    if (_First != _Right.end() && _Where != _First && _Where != ++_Last)
    {       // worth splicing, do it
      _Splice(_Where, _Right, _First, _Last, 1); 
    }
  }

  void splice(iterator _Where, _Myt& _Right,
              iterator _First, iterator _Last)
  {       // splice _Right [_First, _Last) at _Where
    if (_First != _Last && _Where != _Last)
    {       // worth splicing, do it
      size_type _Count = 0;
      if (this == &_Right)
        ;       // just rearrange this list
      else if (_First == _Right.begin() && _Last == _Right.end())
        _Count = _Right.size(); // splice in whole list
      else
        _Count = distance(_First, _Last);       // splice in partial list
      _Splice(_Where, _Right, _First, _Last, _Count); 
    }
  }

  void remove(_ParamTy _Val)
  {       // erase each element matching _Val
    iterator _Last = end();
    for (iterator _First = begin(); _First != _Last; )
      if (*_First == _Val)
        erase(_First++);
      else
        ++_First; 
  }

  template<class _Pr1>
  void remove_if(_Pr1 _Pred)
  {       // erase each element satisfying _Pr1
    iterator _Last = end();
    for (iterator _First = begin(); _First != _Last; )
      if (_Pred(*_First))
        erase(_First++);
      else
        ++_First; 
  }

  void unique()
  {       // erase each element matching previous
    iterator _First = begin(), _Last = end();
    if (_First != _Last)
      for (iterator _Next = _First; ++_Next != _Last; _Next = _First)
        if (*_First == *_Next)
          erase(_Next);
        else
          _First = _Next; 
  }

  template<class _Pr2>
  void unique(_Pr2 _Pred)
  {       // erase each element satisfying _Pred with previous
    iterator _First = begin(), _Last = end();
    if (_First != _Last)
      for (iterator _Next = _First; ++_Next != _Last; _Next = _First)
        if (_Pred(*_First, *_Next))
          erase(_Next);
        else
          _First = _Next; 
  }

  void merge(_Myt& _Right)
  {       // merge in elements from _Right, both ordered by operator<
    if (&_Right != this)
    {       // safe to merge, do it
      iterator _First1 = begin(), _Last1 = end();
      iterator _First2 = _Right.begin(), _Last2 = _Right.end();

      while (_First1 != _Last1 && _First2 != _Last2)
        if (*_First2 < *_First1)
        {       // splice in an element from _Right
          iterator _Mid2 = _First2;
          _Splice(_First1, _Right, _First2, ++_Mid2, 1);
          _First2 = _Mid2; 
        }
        else
          ++_First1;

      if (_First2 != _Last2)
        _Splice(_Last1, _Right, _First2, _Last2,
                _Right._Mysize);      // splice remainder of _Right
    }
  }

  template<class _Pr3>
  void merge(_Myt& _Right, _Pr3 _Pred)
  {       // merge in elements from _Right, both ordered by _Pred
    if (&_Right != this)
    {       // safe to merge, do it
      iterator _First1 = begin(), _Last1 = end();
      iterator _First2 = _Right.begin(), _Last2 = _Right.end();

      while (_First1 != _Last1 && _First2 != _Last2)
        if (_Pred(*_First2, *_First1))
        {       // splice in an element from _Right
          iterator _Mid2 = _First2;
          _Splice(_First1, _Right, _First2, ++_Mid2, 1);
          _First2 = _Mid2; 
        }
        else
          ++_First1;

      if (_First2 != _Last2)
        _Splice(_Last1, _Right, _First2, _Last2,
                _Right._Mysize);      // splice remainder of _Right
    }
  }

private:
  template<typename _Pred>
  static _Nodeptr _SortMerge(_Nodeptr _A, _Nodeptr _B, _Pred _Pr)
  {
    _Nodeptr _R = NULL;
    _Nodeptr _L = NULL;
    _Nodeptr _X;

    while (_A != NULL && _B != NULL)
    {
      if (_Pr(_Myval(_B), _Myval(_A)))
      {
        _X = _B;
        _B = _Next(_B);
      }
      else
      {
        _X = _A;
        _A = _Next(_A);
      }
      if (_L == NULL)
        _R = _L = _X;
      else
      {
        _Next(_L) = _X;
        _L = _X;
      }
    }

    if (_A != NULL)
      _B = _A;
    if (_B != NULL)
    {
      if (_L == NULL)
        _R = _B;
      else
        _Next(_L) = _B;
    }

    return _R;
  }

  template<typename _Pred>
  static _Nodeptr _SortStep(size_type _N, _Nodeptr * _List, _Pred _Pr)
  {
    switch (_N)
    {
    case 0:
      return NULL;
    case 1:
      {
        _Nodeptr _P = *_List;
        *_List = _Next(*_List);
        _Next(_P) = NULL;
        return _P;
      }
#if 0
    case 2:
      {
        _Nodeptr _X = *_List;
        _Nodeptr _Y = _Next(_X);
        _Nodeptr _P = _X;
        *_List = _Next(_Y);
        if (_Pr(_Myval(_Y), _Myval(_X)))
        {
          _Next(_Y) = _X;
          _Next(_X) = NULL;
          _P = _Y;
        }
        else
          _Next(_Y) = NULL;
        return _P;
      }
#endif
    default:
      {
        size_type _J = _N / 2;
        _N -= _J;
        _Nodeptr _A = _SortStep(_J, _List, _Pr);
        _Nodeptr _B = _SortStep(_N, _List, _Pr);
        return _SortMerge(_A, _B, _Pr);
      }
    }
  }

public:
  template<typename _Pred>
  void sort(_Pred _Pr)
  {       // order sequence, using operator<
    _Nodeptr _Unsorted = _Next(_Head());
    _Nodeptr _Sorted = _SortStep(size(), &_Unsorted, _Pr);
    // Make circular again.
    _Nodeptr _P = _Head();
    while (_Sorted != NULL)
    {
      _Next(_P) = _Sorted;
      _Prev(_Sorted) = _P;
      _P = _Sorted;
      _Sorted = _Next(_Sorted);
    }
    _Next(_P) = _Head();
    _Prev(_Head()) = _P;
  }

  void sort()
  {
    sort(less<_Ty>());
  }

  void reverse()
  {       // reverse sequence
    _Mybase::_Reverse();
  }

protected:
  void _Assign_n(size_type _Count, _ParamTy _Val)
  {       // assign _Count * _Val
    // in case _Val is in sequence
    typename _ClassUtil::_TmpHolder<_Ty>::_Type _Tmp(_Val);
    erase(begin(), end());
    _Insert_n(begin(), _Count, _Tmp); 
  }

  _Nodeptr _Buynode(_Nodeptr _Next, _Nodeptr _Prev, _ParamTy _Val)
  {       // allocate a node and set links
    _Nodeptr _Pnode = this->_Alnod().allocate(1);
    _TRY_BEGIN
      typedef typename _TypeUtil::_CopyMemory<_Ty, void>::_Type
              _Void_type;
      new ((_Void_type *)_Pnode) _Node(_Next, _Prev, _Val);
    _CATCH_ALL
      this->_Alnod().deallocate(_Pnode, 1);
    _RERAISE;
    _CATCH_END
    return (_Pnode); 
  }

  void _Tidy()
  {       // free all storage
    erase(begin(), end());
  }

  void _Insert_n(iterator _Where, size_type _Count, _ParamTy _Val)
  {       // insert _Count * _Val at _Where
    size_type _Countsave = _Count;

    _TRY_BEGIN
    for (; 0 < _Count; --_Count)
      _Insert(_Where, _Val);
    _CATCH_ALL
    for (; _Count < _Countsave; ++_Count)
    {       // undo inserts
      iterator _Before = _Where;
      erase(--_Before); 
    }
    _RERAISE;
    _CATCH_END 
  }

  void _Splice(iterator _Where, _Myt& _Right,
               iterator _First, iterator _Last, size_type _Count)
  {       // splice _Right [_First, _Last) before _Where
    if (this->_Alval() == _Right._Alval())
    {       // same allocator, just relink
      if (this != &_Right)
      {       // splicing from another list, adjust counts
        _Incsize(_Count);
        _Right._Mysize -= _Count; 
      }
      _Next(_Prev(_First._Mynode())) = _Last._Mynode();
      _Next(_Prev(_Last._Mynode())) = _Where._Mynode();
      _Next(_Prev(_Where._Mynode())) = _First._Mynode();
      _Nodeptr _Pnode = _Prev(_Where._Mynode());
      _Prev(_Where._Mynode()) = _Prev(_Last._Mynode());
      _Prev(_Last._Mynode()) = _Prev(_First._Mynode());
      _Prev(_First._Mynode()) = _Pnode; 
    }
    else
    {       // different allocator, copy nodes then erase source
      insert(_Where, _First, _Last);
      _Right.erase(_First, _Last); 
    }
  }

  void _Incsize(size_type _Count)
  {       // alter element count, with checking
    _Mybase::_Incsize(_Count);
  }

};

// list TEMPLATE OPERATORS
template<class _Ty, class _Alloc> inline
void swap(list<_Ty, _Alloc>& _Left, list<_Ty, _Alloc>& _Right)
{       // swap _Left and _Right lists
  _Left.swap(_Right); 
}

template<class _Ty, class _Alloc> inline
bool operator==(const list<_Ty, _Alloc>& _Left,
                const list<_Ty, _Alloc>& _Right)
{       // test for list equality
  return (_Left.size() == _Right.size()
          && equal(_Left.begin(), _Left.end(), _Right.begin())); 
}

template<class _Ty, class _Alloc> inline
bool operator!=(const list<_Ty, _Alloc>& _Left,
                const list<_Ty, _Alloc>& _Right)
{       // test for list inequality
  return (!(_Left == _Right)); 
}

template<class _Ty, class _Alloc> inline
bool operator<(const list<_Ty, _Alloc>& _Left,
               const list<_Ty, _Alloc>& _Right)
{       // test if _Left < _Right for lists
  return (lexicographical_compare(_Left.begin(), _Left.end(),
                                  _Right.begin(), _Right.end())); 
}

template<class _Ty, class _Alloc> inline
bool operator>(const list<_Ty, _Alloc>& _Left,
               const list<_Ty, _Alloc>& _Right)
{       // test if _Left > _Right for lists
  return (_Right < _Left); 
}

template<class _Ty, class _Alloc> inline
bool operator<=(const list<_Ty, _Alloc>& _Left,
                const list<_Ty, _Alloc>& _Right)
{       // test if _Left <= _Right for lists
  return (!(_Right < _Left)); 
}

template<class _Ty, class _Alloc> inline
bool operator>=(const list<_Ty, _Alloc>& _Left,
                const list<_Ty, _Alloc>& _Right)
{       // test if _Left >= _Right for lists
  return (!(_Left < _Right)); 
}
#pragma language = restore

_STD_END
#endif /* _LIST_ */

/*
 * This file is derived from software bearing the following
 * restrictions:
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this
 * software and its documentation for any purpose is hereby
 * granted without fee, provided that the above copyright notice
 * appear in all copies and that both that copyright notice and
 * this permission notice appear in supporting documentation.
 * Hewlett-Packard Company makes no representations about the
 * suitability of this software for any purpose. It is provided
 * "as is" without express or implied warranty.
 */

/*
 * Copyright (c) 1992-2009 by P.J. Plauger.  ALL RIGHTS RESERVED.
 * Consult your license regarding permissions and restrictions.
 V5.04:0576 */
